11.1 KB · ⇊ 7 parts · ⤓ Micron 11.1 KB · ⤓ HTML 56.3 KB

top

The multi-commodity flow problem is a network flow problem with multiple commodities (flow demands) between different source and sink nodes.

• Definition

• Corresponding optimization problems

• Relation to other problems

• Usage

• Solutions

• Applications

• External resources

• References

Given a flow network G ( V , E ) {\displaystyle \,G(V,E)} , where edge ( u , v ) ∈ ∈ E {\displaystyle (u,v)\in E} has capacity c ( u , v ) {\displaystyle \,c(u,v)} . There are k {\displaystyle \,k} commodities K 1 , K 2 , … … , K k {\displaystyle K_{1},K_{2},\dots ,K_{k}} , defined by K i = ( s i , t i , d i ) {\displaystyle \,K_{i}=(s_{i},t_{i},d_{i})} , where s i {\displaystyle \,s_{i}} and t i {\displaystyle \,t_{i}} is the source and sink of commodity i {\displaystyle \,i} , and d i {\displaystyle \,d_{i}} is its demand. The variable f i ( u , v ) {\displaystyle \,f_{i}(u,v)} defines the fraction of flow i {\displaystyle \,i} along edge ( u , v ) {\displaystyle \,(u,v)} , where f i ( u , v ) ∈ ∈ [ 0 , 1 ] {\displaystyle \,f_{i}(u,v)\in [0,1]} in case the flow can be split among multiple paths, and f i ( u , v ) ∈ ∈ { 0 , 1 } {\displaystyle \,f_{i}(u,v)\in \{0,1\}} otherwise (i.e. "single path routing"). Find an assignment of all flow variables which satisfies the following four constraints:

(1) Link capacity: The sum of all flows routed over a link does not exceed its capacity.

∀ ∀ ( u , v ) ∈ ∈ E : ∑ ∑ i = 1 k f i ( u , v ) ⋅ ⋅ d i ≤ ≤ c ( u , v ) {\displaystyle \forall (u,v)\in E:\,\sum _{i=1}^{k}f_{i}(u,v)\cdot d_{i}\leq c(u,v)}

(2) Flow conservation on transit nodes: The amount of a flow entering an intermediate node u {\displaystyle u} is the same that exits the node.

∀ ∀ i ∈ ∈ { 1 , … … , k } : ∑ ∑ ( u , w ) ∈ ∈ E f i ( u , w ) − − ∑ ∑ ( w , u ) ∈ ∈ E f i ( w , u ) = 0 w h e n u ≠ ≠ s i , t i {\displaystyle \forall i\in \{1,\ldots ,k\}:\,\sum _{(u,w)\in E}f_{i}(u,w)-\sum _{(w,u)\in E}f_{i}(w,u)=0\quad \mathrm {when} \quad u\neq s_{i},t_{i}}

(3) Flow conservation at the source: A flow must exit its source node completely.

∀ ∀ i ∈ ∈ { 1 , … … , k } : ∑ ∑ ( u , w ) ∈ ∈ E f i ( s i , w ) − − ∑ ∑ ( w , u ) ∈ ∈ E f i ( w , s i ) = 1 {\displaystyle \forall i\in \{1,\ldots ,k\}:\,\sum _{(u,w)\in E}f_{i}(s_{i},w)-\sum _{(w,u)\in E}f_{i}(w,s_{i})=1}

(4) Flow conservation at the destination: A flow must enter its sink node completely.

∀ ∀ i ∈ ∈ { 1 , … … , k } : ∑ ∑ ( u , w ) ∈ ∈ E f i ( w , t i ) − − ∑ ∑ ( w , u ) ∈ ∈ E f i ( t i , w ) = 1 {\displaystyle \forall i\in \{1,\ldots ,k\}:\,\sum _{(u,w)\in E}f_{i}(w,t_{i})-\sum _{(w,u)\in E}f_{i}(t_{i},w)=1}

Load balancing is the attempt to route flows such that the utilization U ( u , v ) {\displaystyle U(u,v)} of all links ( u , v ) ∈ ∈ E {\displaystyle (u,v)\in E} is even, where

U ( u , v ) = ∑ ∑ i = 1 k f i ( u , v ) ⋅ ⋅ d i c ( u , v ) {\displaystyle U(u,v)={\frac {\sum _{i=1}^{k}f_{i}(u,v)\cdot d_{i}}{c(u,v)}}}

The problem can be solved e.g. by minimizing ∑ ∑ u , v ∈ ∈ V ( U ( u , v ) ) 2 {\displaystyle \sum _{u,v\in V}(U(u,v))^{2}} . A common linearization of this problem is the minimization of the maximum utilization U m a x {\displaystyle U_{max}} , where

∀ ∀ ( u , v ) ∈ ∈ E : U m a x ≥ ≥ U ( u , v ) {\displaystyle \forall (u,v)\in E:\,U_{max}\geq U(u,v)}

In the minimum cost multi-commodity flow problem, there is a cost a ( u , v ) ⋅ ⋅ f ( u , v ) {\displaystyle a(u,v)\cdot f(u,v)} for sending a flow on ( u , v ) {\displaystyle \,(u,v)} . You then need to minimize

∑ ∑ ( u , v ) ∈ ∈ E ( a ( u , v ) ∑ ∑ i = 1 k f i ( u , v ) ⋅ ⋅ d i ) {\displaystyle \sum _{(u,v)\in E}\left(a(u,v)\sum _{i=1}^{k}f_{i}(u,v)\cdot d_{i}\right)}

In the maximum multi-commodity flow problem, the demand of each commodity is not fixed, and the total throughput is maximized by maximizing the sum of all demands ∑ ∑ i = 1 k d i {\displaystyle \sum _{i=1}^{k}d_{i}}

The minimum cost variant of the multi-commodity flow problem is a generalization of the minimum cost flow problem (in which there is merely one source s {\displaystyle s} and one sink t {\displaystyle t} ). Variants of the circulation problem are generalizations of all flow problems. That is, any flow problem can be viewed as a particular circulation problem.cite-ref-ahuja-et-al-1993-1-0[1]

Routing and wavelength assignment (RWA) in optical burst switching of Optical Network would be approached via multi-commodity flow formulas, if the network is equipped with wavelength conversion at every node.

Register allocation can be modeled as an integer minimum cost multi-commodity flow problem: Values produced by instructions are source nodes, values consumed by instructions are sink nodes and registers as well as stack slots are edges.cite-ref-2[2]

In the decision version of problems, the problem of producing an integer flow satisfying all demands is NP-complete,cite-ref-eis76-3-0[3] even for only two commodities and unit capacities (making the problem strongly NP-complete in this case).

If fractional flows are allowed, the problem can be solved in polynomial time through linear programming,cite-ref-4[4] or through (typically much faster) fully polynomial time approximation schemes.cite-ref-5[5]

Multicommodity flow is applied in the overlay routing in content delivery.cite-ref-6[6]

• Papers by Clifford Stein about this problem: http://www.columbia.edu/~cs2035/papers/#mcf

• Software solving the problem: https://web.archive.org/web/20130306031532/http://typo.zib.de/opt-long_projects/Software/Mcf/

cite-note-ahuja-et-al-1993-11. ↑ citerefahujamagnantiorlin1993Ahuja, Ravindra K.; Magnanti, Thomas L.; Orlin, James B. (1993). Network Flows. Theory, Algorithms, and Applications. Prentice Hall.

cite-note-22. ↑ citerefkoes2009Koes, David Ryan (2009). "Towards a more principled compiler: Register allocation and instruction selection revisited" (PhD). Carnegie Mellon University. S2CID 26416771.

cite-note-eis76-33. ↑ citerefs-even-and-a-itai-and-a-shamir1976S. Even and A. Itai and A. Shamir (1976). "On the Complexity of Timetable and Multicommodity Flow Problems". SIAM Journal on Computing. 5 (4). SIAM: 691–703. doi:10.1137/0205048.citerefevenitaishamir1975Even, S.; Itai, A.; Shamir, A. (1975). "On the complexity of time table and multi-commodity flow problems". 16th Annual Symposium on Foundations of Computer Science (SFCS 1975). pp. 184–193. doi:10.1109/SFCS.1975.21. S2CID 18449466.

cite-note-44. ↑ citerefthomas-h-cormen-charles-e-leiserson-ronald-l-rivest-and-clifford-stein2009Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein (2009). "29". Introduction to Algorithms (3rd ed.). MIT Press and McGraw–Hill. p. 862. ISBN 978-0-262-03384-8.{{cite book}}: CS1 maint: multiple names: authors list (link)

cite-note-55. ↑ citerefgeorge-karakostas2002George Karakostas (2002). "Faster approximation schemes for fractional multicommodity flow problems". Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms. pp. 166–173. ISBN 0-89871-513-X.

cite-note-66. ↑ Algorithmic Nuggets in Content Delivery sigcomm.org

Add: Jean-Patrice Netter, Flow Augmenting Meshings: a primal type of approach to the maximum integer flow in a multi-commodity network, Ph.D dissertation Johns Hopkins University, 1971